1. Field of the Invention
The present invention is in the field of communication apparatus and methods. Generally, the invention relates to processing and organizing digital information for communication from one location to another. More specifically, this invention relates to use of asynchronous transfer mode in a communication network to communicate information. The communicated information is processed and organized in apparatus and according to methods disclosed herein. Still more particularly, the present invention relates to an ATM communication system interconnect/termination unit (hereinafter, "ATMCSI/TU").
2. Related Technoloqy
Asynchronous Transfer Mode (ATM) is a network protocol which is highly advantageous because it allows high speed transmission of divergent types of data, including digital codes, video, and voice. This is accomplished by breaking down incoming digital data to be transmitted into units of constant size. These units are called cells, and include a 48-octet field containing the actual data; along with a header field, for a total of 53 octets in the cell. A Conversion Sublayer Protocol Data Unit (CS-PDU) may have both a header and a trailer of additional information, and may be as long as 64K bits The process of communicating these cells involves taking digital data and segmenting it into cell-size units and assembling these units into CS-PDU's. At interconnections, the CS-PDU's are segmented and reassembled to route cells to their destinations in accord with the communication traffic load of the network, the class of service for the senders of the cells, and a variety of other parameters familiar to those skilled in the pertinent arts.
The header contains a virtual channel identifier and a virtual path identifier which identify the particuLar cell and its intended destination, and specify an optimal path through the network along which the cell should be routed to reach its destination. The header can also include numerous other information such as the type of data in the CS-PDU and attributes of the data, the sender and/or the destination. In combination, the virtual path identifier and virtual channel identifier define a virtual circuit within the network. This virtual circuit is unlike the old and well known actual hard-wired communication circuits of conventional telephone and data transmission systems, for example, because it does not actually provide a fixed or constant communication path (i.e., an electrical conductor, twisted-pair conductors, radio link, or fiber-optic light conductor, for example) continuously extending between the end points. A virtual circuit is continually reconfigured (i.e., possibly following a succession of several different alternative network paths) as the operating circumstances of the network change dynamically.
The ATM-protocol data may be transmitted along a digital electronic data network. A series of cells or packets communicated between endpoints of the network effectively provides a communication circuit between these endpoints. Such communication networks are becoming increasing widespread. These networks allow for the communication of divergent types of data including computer-coded text and graphics, voice, music, images, and video. Such networks enable the interconnection of large numbers of computer work stations, telephone, television systems, video teleconferencing systems, and other facilities over common data links or carriers.
Computer work stations are typically interconnected by local area networks (LAN) such as Ethernet, Token Ring, DECNet and RS-232, whereas metropolitan, national and international systems are interconnected by wide area networks (WAN) such as T1, V3.5 and FDDI.
LANs and WANs themselves can be interconnected by devices known as hubs, bridges and routers in an unlimited configuration. Although the distinction between these interconnection devices is becoming increasingly arbitrary, they are officially classified in accordance with the layer in the Open Systems Interconnection (OSI) model in which they operate.
Hubs interconnect devices using the Physical Layer, bridges utilize the Data Link layer, whereas routers operate using the Network layer. Hubs and bridges generally act merely as switches or funnels, whereas routers perform higher level functions including selecting optimal routes through the network for transmission of data packets or cells on an individual basis, and performing network management tasks such as forcing diagnostics operations and controlling other routers or nodes. Whereas hubs and bridges generally operate on data which is formatted in a single protocol such as those listed above (i.e., uni-protocol), routers can typically identify and process data which can be in any one of several protocols (multi-protocol).
Interconnect devices, especially the more sophisticated routers, have typically been large, bulky and expensive units which operate at relatively low speed. As such, they limit the data throughput speed in the network in which they are installed. The reasons why routers have been so slow is that they are generally multi-chip units which transfer data being processed to and from Content Addressable Memory (CAM) chips which are separate from the processor, input/output (I/O) and other functional chips of the unit. These data-transfer operations each require multiple system clock cycles which fundamentally limit the data transfer speed. In addition, multiple latencies are present in the various paths by which data moves through the unit. The degree by which such latencies can be reduced, as well as the degree by which the size and cost of a multi-chip system can be reduced, are also fundamentally limited.
It should be recalled that the digital communication connections (i.e., virtual circuits) maintained by an ATM system may belong to different classes of service. The reasons for these differing classes of service have to do with the differing types of digital data being communicated. Video connections, for example, do not require the same class of service as do file transfers. A file transfer is not sensitive to delay, while a video connection certainly is sensitive to transmission delay. Similarly, an audio connection is not sensitive to cell loss, while a file transfer is very sensitive to cell loss. With an audio connection, the loss of a cell in not noticeable to the recipient of the conversation because the human ear is not sensitive enough to detect the small gap in the conversation. The human ear takes meaning from context, so that a small gap in the sound of a word would probably not even be noticed. On the other hand, a file transfer is very sensitive to loss of a cell. A missing cell from a file transfer means that the received file is deficient and incomplete, and that the file data may be meaningless without the missing data.
Consequently, differing classes of service are provided to users of ATM systems. One class of service is constant-bit-rate (CBR) service, and is commonly used for audio communications and un-compressed video information. With constant-bit-rate service a cell is transmitted from a given connection on a regularly repeating time interval, perhaps one cell every couple of microseconds. Another class of service is variable-bit-rate (VBR) service, and is commonly used to transmit compressed video data. The cell rate in this instance is variable dependent on the video compression technique in use and the video image contents (i.e., rate of video image change or frames per second). Understandably, managing these variable-bit-rate services becomes a burdensome task when a multitude of connections (perhaps in the thousands) are being maintained simultaneously.
A conventional asynchronous transfer mode (ATM) speech-path switching system is depicted in U.S. Pat. No. 4,956,839, issued Sep. 11, 1990 to Torii Yutaka, et al. The '839 patent is believed to disclose an ATM line terminating apparatus serving to physically terminate a transmission line and to perform processing of received information in ATM format. That is, information contained in a header filed of a received cell or packet is processed. The ATM terminating apparatus includes a cell-phase synchronizing circuit for matching the temporal positions of cells in each of the lines; and a flow monitor circuit for performing control to avoid overload of the subscriber terminal according to a service agreement, for example.
Another conventional ATM switch and multiplexer is known in accord with U.S. Pat. No. 5,189,668, issued Feb. 23, 1993 to Mashiro Takatori, et al. The '668 patent is believed to disclose an ATM switch having a plurality of concentration space-division switches each constituted with an multi-stage connection of switch modules. Each of the switch modules in a stage includes a certain number of buffers and a selector for arbitrating outputs from the buffers. Each stage includes switch modules of a number at most equal to the certain number of buffers of the stage multiplied by the number of switch modules in a preceding stage. The multiple stages include a final stage with a singular switch module.
Still another conventional ATM switching system and adaption processing apparatus is disclosed in U.S. Pat. No. 5,214,642, issued May 25, 1993 to Masao Kunimoto, et. al. The ATM apparatus of the '642 patent is believed to include an adaption-processing apparatus for assembling received data units of fixed length to provide variable-length data units. These variable-length data units are transmitted to a plurality of variable-length data unit processors while assembling variable-length data units received from the plurality of variable-length data unit processors to provide fixed-length data units for transmission therefrom. This ATM switching system includes an adaptation processing apparatus, a signal processing unit having a plurality of the variable-length data unit processors, and first-in-first-out (FIFO) memory for the variable-length data units provided from the adaptation process.
Further, a conventional ATM network device is known in accord with U.S. Pat. No. 5,220,563, issued Jun. 15, 1993 to Thierry Grenot, et al. The '563 patent is believed to relate to a device for acquiring the signalling data elements of each channel of multi-frame data, and for detecting he changes in state of these data elements. A device generates an information cell on the network for each change thuds detected, with the information cell including the new signalling data elements. The information cell also includes the address information associated with the corresponding channel. A device is included for receiving and memorizing the information cells from the network, and for inserting the data elements thus memorized into a multi-frame for transmission synchronously in out-of-band mode.
Another interconnection system to which the invention generally relates is disclosed in U.S. Pat. No. 5,218,680, issued Jun. 8, 1993 to J. Farrell et al.
Generally, the conventional technology for ATM termination and interconnection devices can be characterized as offering users only two choices in architecture. One architecture implemented all functions in hardware and was not flexible to evolving technology and situations as the uses of ATM develop. The other architecture executed all commands in software, so that the users of the device could program their choices with respect to how the device functioned in particular situations. However, because all of the commands and CS-PDU processing operations were performed in software by using a processing unit, the devices were slow, and represented a bottleneck in the system. That is, under conditions of heavy or complex traffic, the processor simply was not able to execute enough instructions and process enough CS-PDU's to keep up with demand.
In ATM technology there is a concept of virtual connections. These might be though of as a virtual pipeline connecting users of the network, but each pipeline serves more than one pair of users. That is, traffic from several users flows along the same pipeline interspersed with one another in fragments. As an example, a computer video session between two users might go through one pipeline, while a fiLe transfer between two other users is also going on through the same pipeline. Each of these communications would use different virtual connections, although they would both go through the same physical structure (i.e., fiber optic cable or twisted-pair telephone lines, for example). In the conventional technology, all the processing could be commanded by software (with the speed limitation alluded to above), or by hardware (with the ATM system having a rigidity in its nature because changing the abilities of the system required new hardware).
A disadvantage of the related technology arises from old methods of implementing a first-in-first-out (FIFO) memory. Traditionally, FIFO memories have been implemented by using one of a "fall through", or a "memory and counter" architectures. With a fall through architecture, a set of cascaded registers are used, and new data entered into the FIFO falls through the registers until it reaches the last free location. When data is read from the FIFO memory, it is taken from the bottom register, and the content of the other higher registers has to be rewritten successively one register down in the cascade of registers. In the memory and counter implementation, of a FIFO memory, a memory area with register locations, along with separate read and write counters, are maintained. Data elements are written into memory register locations pointed to by the write counter, and read from locations pointed to by the read counter. The counters are individually incremented one register location along the list after each respective read or write operation. After reaching the end of list, the counters rotate individually to the beginning of the memory register locations so that FIFO operation is maintained.
A disadvantage of these conventional FIFO memory implementations results from the inability to either insert new data into the memory, or to remove data from the memory, except at the tail or head end of the list, respectively. However, in ATM operations, including SAR operations in association with receiving or transmitting cells, it is necessary to alter the order of cell reassembly and transmission, for example, in response to the requirements to provide differing classes of ATM service, and to prevent loss of cells from an un-interruptable service during intervals of network conflict or congestion.
Another disadvantage of the conventional technology stems from the conventional calendar structures used to schedule future events in the device. The conventional calendar structures include an array of cell slots with an event pointer that advances one array position for each cell slot time interval. Events that need to be scheduled at a future time have their event descriptor attached to the appropriate location in the array. This attachment may be effected by use of a linked list, for example. When the event pointer gets to the location of a particular event, the event is then scheduled. In case more than one event is scheduled in the same cell slot, then the event descriptors for the events are linked together by means of the linked list structure. A significant disadvantage of the conventional calendar method is that memory requirements are excessive. For example, if the rates of events to be supported is large, a minimum rate of 1 cell/sec for an OC-3 link at 150 mbps, for example, requires an array of 353,000 entries. Because each entry has a head and a tail pointer with four bytes for each, the total memory requirement is 2.82 Mbytes just for a calendar.